package 动态规划.棋盘dp;

import java.util.concurrent.locks.ReentrantLock;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/8/10 21:12
 */
public class lc980不同路径III {

    /*
     这题 还能      状态压缩 + 记忆化搜索呢！
     https://leetcode.cn/problems/unique-paths-iii/solutions/2372252/liang-chong-fang-fa-hui-su-zhuang-tai-ya-26py/
     */



    int begin_x,begin_y,count_0 = 0;
    public int solve(int grid[][]){
        for(int i = 0;i < grid.length;i++){
            for (int j = 0; j < grid[0].length; j++) {
                if(grid[i][j] == 1){
                    begin_x = i;
                    begin_y = j;
                }
                else if(grid[i][j] == 0){
                    count_0++;
                }
            }
        }
        int dfs = dfs(begin_x, begin_y, grid, new boolean[grid.length][grid[0].length], -1); // 起点也要算上, 多算了一个点， 所以一直不对， 需要把起点给排除掉！
        return dfs;
    }

    public int dfs(int i,int j,int grid[][],boolean vis[][],int count){
        if(i < 0 || j < 0 || i == grid.length || j == grid[0].length || vis[i][j] || grid[i][j] == -1){
            return 0;
        }
        if(grid[i][j] == 2 ){
            return count == count_0 ? 1 : 0;
        }
        /*
         这样写 ， 会多走 很多 无用的 路， 因为终点 也只能走一次！
         */
//        if(grid[i][j] == 2 && count == count_0){
//            return 1;
//        }

        // 走到这里 说明 是 无障碍方格
        int ans ;
        vis[i][j] = true;
        ans = dfs(i - 1,j,grid,vis,count + 1);
        ans += dfs(i + 1,j,grid,vis,count + 1);
        ans += dfs(i,j - 1,grid,vis,count + 1);
        ans += dfs(i,j + 1,grid,vis,count + 1);
        vis[i][j] = false;
        return ans;
    }



    private static ReentrantLock lock = new ReentrantLock();

    public static void main(String[] args) {
        // 创建多个线程进行锁竞争
        for (int i = 1; i <= 2; i++) {
            Thread thread = new Thread(new Worker(),"t" + i);
            thread.start();
        }
        System.out.println("end");
    }

    static class Worker implements Runnable {
        @Override
        public void run() {
            try {
                // 尝试获取锁
                lock.lock();
                System.out.println("Thread " + Thread.currentThread().getId() + " has acquired the lock.");
                // 模拟线程执行一段时间
                Thread.sleep(200000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                // 释放锁
                lock.unlock();
                System.out.println("Thread " + Thread.currentThread().getId() + " has released the lock.");
            }
        }
    }
}

class X{
    static String s = "hello0";
    private static Integer x = 10;
}